/*
 * Algorithm.java
 * @author Andrey Tesler
 * Created for DiffView project
 * Created on 4 October 2009, 13:53
 */

package diffview;

import java.util.*;
import static java.lang.Math.*;
import static java.lang.System.*;

/**
 * This is an algorithm which finds one of the "shortest paths" 
 * between oldLines and newLines. 
 * Each path consists of transformations of four kinds: <ul>
 * <li> delete an old line (its cost is the weight of the deleting line);
 * <li> insert a new line (its cost is the weight of the inserting line);
 * <li> replace an old line with a new one (its cost is only a bit fewer 
 *      than the cost of removing the first line 
 *      plus the cost of inserting of the second one);
 * <li> do nothing if the lines coincides (its cost is 0).
 * </ul>
 *
 * The length of a path is the sum of all costs of the transformation.
 * As for weights of lines, in current implementation they depends only 
 * on their lengths (but I plan to change it).
 */
public class Algorithm implements IAlgorithm {
    
    private List<String> oldLines, newLines;
    
    /* It's the weight of strings of old/new file. */
    private double[] deletionCosts, insertionCosts;
    
    /*It's the distance between oldLines.get(i) and newLines.get(j). */
    private double[][] replacementCosts;
    
    /* These are the distances between "tail" sublists:
     * oldLines.sublist(i, oldLines.size()) 
     * and newLines.sublist(j, newLines.size()). 
     * So the size of this array is (oldLinesCount + 1) * (newLinesCount + 1):
     * the last row and the last column denote the distance from the empty list
     * to a tail of the other list.
     * In particular, the right lower element of the array denotes the distance 
     * between two empty lists and thus equals to 0.
     */
    private double[][] distancesBetweenSublists;
    private int oldLinesCount, newLinesCount;
    
    /* These are lists for the model. They have nulls for the stings 
     * which are deleted / inserted in the oter list.
     */
    private List<String> oldModelLines, newModelLines;
    
    /** Splits a string to lines using <code>"\n", "\r", "\r\n"</code> 
     * as delimiters.
     */
    static List<String> split(String s) {
        final String DELIMITERS = "\r\n|\r|\n";
        return Arrays.asList
                (s.split(DELIMITERS, 
                       -1 /*don't ignore trailing empty strings! */));
    }
    
    /* If a cost was calculated once, we put it to the array
     * so as not to count it another time.
     * This relates also to the methods getInsertionCost 
     * and getReplacementCost.
     */
    private double getDeletionCost(int number) {
        if (number >= oldLinesCount) {
            return Double.MAX_VALUE; //cannot delete it
        }
        if (deletionCosts[number] == -1) {
            deletionCosts[number]
                    = log10(6 + oldLines.get(number).length()); //for example
        }
        return deletionCosts[number];
    }    
    
    private double getInsertionCost(int number) {
        if (number >= newLinesCount) {
            return Double.MAX_VALUE; //cannot insert it
        }
        if (insertionCosts[number] == -1) {
            insertionCosts[number]
                    = log10(6 + newLines.get(number).length()); //for example
        }
        return insertionCosts[number];
    }
    
    /* If two lines coincides, this cost is 0. */
    private double getReplacementCost(int oldLine, int newLine) {
        if (oldLine >= oldLinesCount || newLine >= newLinesCount) {
            return Double.MAX_VALUE; // cannot replace them
        }
        if (replacementCosts[oldLine][newLine] == -1) {
            // not an ideal variant, but it's better than nothing:
            // TODO find the greatest common subsequence
            // of symbols/syntax elements/syntax elements with weights
            replacementCosts[oldLine][newLine] = 
                    (oldLines.get(oldLine).equals(newLines.get(newLine))) 
                    ? 0 // the strings are equal!
                    : getDeletionCost(oldLine) + getInsertionCost(newLine)
                        - 1e-8; // only a bit better than removing + inserting
        }
        return replacementCosts[oldLine][newLine];
    }        
    
    
    private double getDistanceBetweenSublists(int i, int j) {
        if (i > oldLinesCount || j > newLinesCount) {
            return Double.MAX_VALUE; // don't go to this domain!
        }
        if (distancesBetweenSublists[i][j] != -1) {
            return distancesBetweenSublists[i][j];
        }
        
        /* Dynamic programming.
         * If a cost was calculated once, we put it to the respective array
         * so as not to count it another time.
         * The value distancesBetweenSublists[oldLinesCount][newLinesCount] = 0
         * has been set before.
         */
        double result = min(min(
                getDeletionCost(i) + getDistanceBetweenSublists(i+1, j),
                getInsertionCost(j) + getDistanceBetweenSublists(i, j+1)),
                getReplacementCost(i, j) + getDistanceBetweenSublists(i+1, j+1)
                );
        return (distancesBetweenSublists[i][j] = result);
    }
    
    /* Determines if two double numbers are almost equal */
    private static boolean aeq(double x, double y) {
        return (abs(x - y) < 1e-12);
    }
    
    /** {@inheritDoc} */
    public Model createModel(String oldText, String newText) {
        /* Split old and new texts to lines */
        oldLines = split(oldText);
        newLines = split(newText);
        
        /* Some initialization */
        oldLinesCount = oldLines.size();
        newLinesCount = newLines.size();
        oldModelLines = new ArrayList<String>();
        newModelLines = new ArrayList<String>();
        
        /* Initialization of arrays with cost values */        
        deletionCosts = new double[oldLinesCount];
        Arrays.fill(deletionCosts, -1); // the cost is unknown
        insertionCosts = new double[newLinesCount];
        Arrays.fill(insertionCosts, -1);
        replacementCosts = new double[oldLinesCount][newLinesCount];
        for (double[] item : replacementCosts) {
            Arrays.fill(item, -1);
        }
        
        distancesBetweenSublists 
                = new double[oldLinesCount+1][newLinesCount+1]; /* sic! */
        for (double[] item : distancesBetweenSublists) {
            Arrays.fill(item, -1);
        }
        distancesBetweenSublists[oldLinesCount][newLinesCount] 
                = 0; //that's the distance between two empty lists
        
        
        /* Let's count all costs */
        getDistanceBetweenSublists(0, 0);
        
        /* Let's find out the best way between oldLines and newLines 
         * (backward search).
         */
        //TODO I should prefer to perform similar transformations successively:
        // if the previous was, e.g., deletion, I should try to do deletion
        // first of all.
        int i = 0, j = 0;
        while (i < oldLinesCount || j < newLinesCount) {
            if (aeq(getDistanceBetweenSublists(i, j), 
                    getReplacementCost(i, j) 
                    + getDistanceBetweenSublists(i+1, j+1))) {
                oldModelLines.add(oldLines.get(i));
                newModelLines.add(newLines.get(j));
                i++;  j++;
                //modelCorrespondences.add(getReplacementCost(i, j) == 0
                //        ? "M" : "R " + getReplacementCost(i, j);
                continue;
            }
            if (aeq(getDistanceBetweenSublists(i, j), 
                    getDeletionCost(i) + getDistanceBetweenSublists(i+1, j))) {
                oldModelLines.add(oldLines.get(i));
                newModelLines.add(null);
                i++;
                //modelCorrespondences.add("D " + getDeletionCost(i));
                continue;
            }
            if (aeq(getDistanceBetweenSublists(i, j), 
                    getInsertionCost(j) + getDistanceBetweenSublists(i, j+1))) {
                oldModelLines.add(null);
                newModelLines.add(newLines.get(j));
                j++;
                //modelCorrespondences.add("I " + getInsertionCost(i));
                continue;
            }
        }
        
        
        return new Model(oldModelLines, newModelLines 
                /* , modelCorrespondences */);
    }
    
}
